package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class NC134 {
    public class Solution1 {
        //这个贪心策略就有问题
        public int maxProfit (int[] prices) {
            //单调栈？
            Stack<Integer> stack = new Stack<>();
            int max = 0;
            int len = prices.length;
            for (int i = len - 1; i >= 0; i--) {
                while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    max = Math.max(max, stack.peek() - i);
                }
                stack.push(i);
            }
            return max;
        }
    }

    public class Solution {
        public int maxProfit (int[] prices) {
            int last = Integer.MAX_VALUE;
            int sum = 0;
            for (int i = 0; i < prices.length; i++) {
                if (prices[i] > last) {
                    sum += (prices[i] - last);
                }
                last = prices[i];
            }
            return sum;
        }      

        /* 
            状态：
            持有股票与否及其价格
            当前遍历到的位置

            f[i] : 当前遍历到位置的最大利润
        */
        public int dfs(int[] nums, int idx, int cur, int take) {
            if (idx == nums.length) {
                return cur;
            }
            int res = 0;
            if (take != -1) {
                res = dfs(nums, idx + 1, cur, take);
                if (nums[idx] > take) {
                    res = Math.max(dfs(nums, idx + 1, cur + nums[idx], -1),
                    res);
                }
            } else {
                res = Math.max(dfs(nums, idx + 1, cur - nums[idx], nums[idx]),
                dfs(nums, idx + 1, cur, -1));
            }
            return res;
        }

        public int maxProfit1 (int[] prices) {
            return dfs(prices, 0, 0, -1);
        }

        public int maxProfit2 (int[] prices) {
           int max = -1, len = prices.length;
            for (int i = 0; i < len; i++) {
                max = Math.max(max, prices[i]);
            }
            int[][] f = new int[len + 1][max + 1];
            //f[len][i] = 0
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= max; j++) {
                    if (j == 0) {
                        f[i][j] = Math.max(f[i + 1][prices[i]], f[i + 1][0]);
                    }
                }
            }
            return f[0][0];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{2,4,10,57,30,82,90,12,5,13};
        // nums = new int[]{1,2,3,4,5};
        System.out.println(s.maxProfit(nums));
        System.out.println(s.maxProfit1(nums));
    }
}
